package week119;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    class Node {
        int[] location = new int[2];
        int route;

        public Node(int x, int y) {
            location[0] = x;
            location[1] = y;
            this.route = x * x + y * y;
        }
    }

    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> (a.route - b.route));
        for (int[] point : points) {
            pq.add(new Node(point[0], point[1]));
        }
        int[][] res = new int[K][2];
        for (int i = 0; i < K; i++) {
            res[i] = pq.poll().location;
        }
        return res;
    }

    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        int len = A.length;
        for (int i = 0; i < len - 2; i++) {
            if (valid(A[len - i - 2], A[len - i - 3], A[len - i - 1]))
                return A[len - i - 1] + A[len - i - 2] + A[len - i - 3];
        }
        return 0;
    }

    private boolean valid(int a, int b, int c) {
        return a + b > c;
    }

    public int subarraysDivByK(int[] A, int K) {
        int res = 0;
        int sum;
        for (int i = 0; i < A.length; i++) {
            sum = 0;
            for (int i1 = i; i1 < A.length; i1++) {
                sum += A[i1];
                if (sum % K == 0) res++;
            }
        }
        return res;
    }

    private int[] nums;
    private int res;

    public int oddEvenJumps(int[] A) {
        //因为直接到最后一个肯定有结果，所以起初为1
        res = 1;
        //假如是偶数次终止，那么前面是大于等于的
        nums = A;
        dfs(true, A.length - 1, A[A.length - 1]);
        dfs(false, A.length - 1, A[A.length - 1]);
        return res;

    }

    private void dfs(boolean flag, int i, int pre) {
        for (int j = i - 1; j >= 0; j--) {
            if (flag && nums[j] >= pre) {

                dfs(false, j, nums[j]);
                res++;
                int min=nums[j];
                for (int k = j; k >= 0; k--) {
                    if (nums[k] < min && nums[k] >= pre){
                        min=nums[k];
                        dfs(false, k, nums[k]);
                    }
                }
                break;
            } else if (!flag && nums[j] <= pre) {
                dfs(true, j, nums[j]);
                res++;
                int max=nums[j];
                for (int k = j-1; k >= 0; k--) {
                    if (nums[k] > max && nums[k] <= pre){
                        max=nums[k];
                        dfs(true, k, nums[k]);
                        res++;
                    }
                }
                break;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

//        System.out.println(solution.oddEvenJumps(new int[]{10, 13, 12, 14, 15}));
        System.out.println(solution.oddEvenJumps(new int[]{2, 3, 1, 1, 4}));
        System.out.println(solution.oddEvenJumps(new int[]{5, 1, 3, 4, 2}));
//        System.out.println(solution.oddEvenJumps(new int[]{3,6,2,3}));
    }
}
